1. Field of the Invention
The present invention relates generally to computer graphics and more particularly to graphics primitive rasterization.
2. Description of Related Art
In graphic systems, graphic objects are typically constructed with combinations of graphics primitives in a geometrical model definition stage. Graphics primitives may include lines, characters, areas such as triangles and ellipses, and solid or patterned shapes such as polygons, spheres, cylinders and the like. These primitives may be connected together to form two or three-dimensional geometric models of a desired graphics object or scene. Since each graphics primitive of a geometric model is represented by a data structure, the geometric model is a linked data structure stored in memory. Further, each graphics primitive is associated with proper attributes to give the primitive a desired color, shade, texture and transparency.
In raster graphic systems, a scene having one or more graphics objects may be displayed as a raster image made up of picture elements (pixels) organized into horizontal rows (i.e., horizontal scan lines) representing an entire display screen area. Depending on desired resolution, color, brightness and other factors, each pixel may be represented by one or more bits. Similarly, a raster display screen also has pixels organized into horizontal rows to form a grid or array of pixels which may emit a range of colored light to display an image. Thus, in order to display a graphics object, data associated with display screen pixel locations that correspond to graphics primitive pixels must be computed based on information about each primitive. The information includes data related to the display screen pixel coordinates (Xs, Ys), pixel depth (Z), pixel color space (e.g., R, G, B, YIQ, HSV), pixel transparency, and pixel image texture coordinate space (U, V). After rasterization, pixel data corresponding to graphics primitives are stored in a frame buffer usually implemented as arrays of video random access memories (VRAMs). Subsequently, a display controller retrieves the stored rasterized pixel data to intensify corresponding display screen pixel locations, thereby tracing out graphics primitives on the display screen.
The rasterization process generally involves two tasks: graphics primitive decomposition and computation. In the first task, display screen pixels, which correspond to data points inside each graphics primitive image, are identified. In the second task, data related to display screen pixel appearance are computed. Such data include display information such as visible portions of a primitive as viewed from a synthetic camera's point of view and color assignments to each display screen pixel.
Generally, there are two rasterization approaches: object order and image order. In the object order rasterization approach, each primitive is decomposed into pixels. Based on color and visibility of the primitive at each pixel, pixel data in the frame buffer including z-buffer is updated. Alternatively, in the image order rasterization approach, each pixel in the raster image is checked to determine whether any primitives cover the pixel. For each primitive covering the pixel, the primitive's contribution in terms of color, shading, transparency and texture is then computed.
An example of the object order rasterization approach involves an “edge and span traversal” technique. As shown in FIG. 1, a triangular graphics primitive 100 has three vertices V0, V1 and V2 and is intersected by a number of horizontal scan lines (i.e., SCAN LINE1 through SCAN LINE6). Assuming the three vertices V0, V1 and V2 of the primitive 100 are known, slopes of edges 102, 104 and 106 of the primitive 100 can be calculated as follows:m=(Ye−Ys)/(Xe−Xs)  (1)where (Xs, Ys) and (Xe, Ye) are any two vertices of the primitive 100. Starting from a chosen vertex, intersecting points between the edges 102, 104 and 106 of the primitive 100 and horizontal scan lines can be incrementally determined from a corresponding calculated slope value together with a known distance between any two horizontal scan lines under equation (1). By using corresponding intersecting points as starting and end points of intersecting horizontal scan lines, interior points of the primitive 100 can be determined by traversing scan line segments. Additionally, corresponding information on color, depth and texture for each rasterized pixel point may be determined by interpolation based on values at the vertex.
Disadvantageously, determining the three edge slopes in equation (1) requires three separate arithmetic divisions. Further, in traversing the scan line segments, another arithmetic division may be required to determine the traversing increment. In addition to requiring an extra accumulator register, arithmetic division calculations are generally slow. As such, rasterizing using the “edge and span traversal” technique is not the most efficient approach.
An example of the image order rasterization approach involves an edge function technique, as will be described in connection with FIG. 2. Under the edge function technique, an edge function is generated for each of three edges 202, 204 and 206 of an exemplary graphics primitive 200. The edge function is then used to determine whether a pixel is located inside or outside of the primitive 200. A pixel is at least partly inside the primitive 200 if values of all three edge functions are positive. Otherwise, the pixel is outside of the primitive 200. In FIG. 2, the primitive 200 has three vertices V0, V1 and V2. Assuming the three vertices V0, V1 and V2 are known, a locus of points on an edge must satisfy the follow equation:n·(x−x0)=0  (2)where n is a vector normal to the edge and x and x0 are points on the edge.
For the edge 204 connected between vertex V0 (having coordinates (x0, y0)) and V1 (having coordinates (x1, y1)), the normal vector n01 is:n0l=(y1−y0)i+(x0−xl)i  (3)
Substituting equation (3) for n0l and the vertex V0 (x0, y0) into equation (2), edge function e0l(x, y) for the edge 204 can be obtained where:e01(x, y)=(x1y0−x0y1)+(y1−y0)x+(x0−x1)y  (4)
Similarly, for edge 206 between V1(having coordinates (x1, y1)) and V2 (having coordinates (X2, y2)) and the edge 202 between vertex V0 (having coordinates (x0, y0)) and V2 (having coordinates (x2, y2)), respective normal vectors nl2 and n02 are:n12=(y2−y1)i+(x1−x2)j  (5)n02=(y2−y0)i+(X0−X2)j  (6)
Substituting equation (5) and the vertex V2 (x2, y2) into equation (2), and substituting equation (6) and the vertex V0 (x0, y0) into equation (2), edge function el2 (x, y) for the edge 206 and edge function e02 (x, y) for the edge 202, respectively, can be obtained. Edge functions el2 (x, y) and e02 (x, y) are shown below.el2(x,y)=(x12y1−x1y2)+(y2−y1)x+(x1−x2)y  (7)e02(x,y)=(x2y0−x0y2)+(y2−y0)x+(X0−x2)y  (8)
By computing the values of edge functions (4), (7) and (8) at a desired pixel point, a determination can be made as to whether the pixel point lies inside or outside of the primitive 200. For simplicity, edge functions (4), (7) and (8) can be made into a more generic function:e(x,y)=e0+nxx+nyy  (9)where e0 is a constant, nx is the x-component of the normal vector n, and ny is the y-component of the normal vector n.
The edge function technique can also be extended to attributes such as depth, color, transparency and texture. For example, in a depth (z) case, locus of points on a plane must satisfy the following equation:n·(x−x0)=0  (10)where n is a vector normal to an edge, and x and X0 are points on a plane.
Assuming three points x0,x1 and x2 on a plane are known, the vector n normal to the plane can be determined using the following equation:n=(x2−x1)(x1−x0)  (11)orn=((y2−y1)(z1−z0)−(y1−y0)(z2−zl)i+((z2−z1)(xl−x0)−(z1−z0)(x2−x1)j+((x2−x1)(y1−y0)−(x1−x0)(y2−y1)k  (11)
By substituting equation (11) into equation (10), z can be determined based on the following equation:z(x, y)=(n·x0)/nz−(nx/nz)x−(ny/nz)y  (12)
where nx is the x-component, ny is the y-component, and nz is the z-component of the normal vector n. As such, the depth z is a function of (x, y). Once the attributes values (e.g., color, transparency, and texture) at the primitive vertices have been determined, the attribute values at rasterized pixel points can be interpolated using equation (12).
Conventionally, the edge function technique requires the raster screen to be broken up into chunks of equal-sized (e.g., 32×32 pixels) which are individually examined relative to each primitive. The raster screen is broken up in order to reduce memory requirements. This reduction is important given that an external memory is typically used as the frame buffer. However, before a chunk is rasterized, a preliminary test is performed to determine whether the primitive intersects a current raster chunk. By performing this test, an entire raster chunk can be eliminated without having to examine each pixel if there is no intersection between the raster chunk and the primitive. The preliminary test involves examining a bounding-box coverage area or calculating a chunk-to-edge distance.
Generally, the bounding-box coverage test determines whether a rectangle (having horizontal and vertical edges) that bounds vertices of a primitive intersects with a current raster chunk. The bounding-box coverage test can be inexact because while the bounding-box may intersect a chunk, the primitive may not. Alternatively, the chunk-to-edge distance test computes a distance from a center of a current chunk to each edge of a primitive. If the distance to a closest edge is less than or equal to one-half (½) the width of the chunk (e.g., 16 pixels in this example), the primitive intersects the current chunk. Although more exact, the chunk-to-edge test requires more processing due to arithmetic multiplication and addition operations to compute Pythagorean distances.
FIG. 3 is a flowchart 300 illustrating decomposition steps for each raster chunk according to the conventional approach. First in step 302, corner pixels of the raster chunks are examined to determine if a pixel lies inside a graphic primitive. If a pixel is inside the primitive in step 304, then the pixel is stored (step 314). Next in step 316, a total number count of pixels examined is checked to determine if all pixels in the chunk have been examined. If all pixels have been examined, then rasterization of the chunk is complete and a next chunk will be examined. However, if pixels still need to be examined, then in step 318, a search for a neighbor pixel is conducted, and the neighboring pixel is examined to determine if the pixel lies inside the primitive in step 320. The pixel will be stored if it lies inside the primitive. Otherwise, an effort is made to get back inside the primitive by backtracking in step 322.
Alternatively, if no corner pixel is found inside the primitive in step 304, then in step 306, pixels along each edge of the chunk are examined. If a pixel is found to be located within the primitive in step 308, then the pixel is stored in step 314. Alternatively, if no pixel is found within the primitive, a heuristics analysis is performed to choose an interior pixel for examination in step 310. Once again, if the pixel is inside the primitive, it is stored in step 314 and steps 316, 318, 320 and 322 are performed as discussed above. Otherwise, another interior pixel is selected until a pixel lying inside the primitive is found.
Conventional implementation of the edge function technique in decomposing primitives relies heavily on heuristics to, first, find a pixel lying inside the primitive. Upon finding such a pixel, the pixel's successive neighboring pixels are incrementally examined using edge functions to find other pixels that lie inside the primitive. Such searching may be intermittently interrupted for backtracking as a result of straying outside the primitive. Thus, this conventional implementation is rather ad-hoc and may not be effective. Moreover, because the conventional approach is inherently sequential (i.e., one pixel is examined at a time), it is not the most efficient technique given the large number of pixels in each chunk.
Therefore, there is a need for a system and method that allows a primitive to be decomposed into pixels more efficiently.